package com.xiaoxiong.tool;

import com.xiaoxiong.common.bo.ListNode;

import java.util.*;

/**
 * @author: pujx
 * @Date: 2019/5/5 14:55
 * @Description:应用于一些思维的计算方式
 */
public class Solution {


    /**
     * 求两数相加和为目标的索引
     * 避免嵌套循环，这样性能较优
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, len = nums.length; i < len; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return new int[]{};
    }


    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        //正确答案
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        //return dummyHead.next;


        //我的错误做法

        int num1 = getNumByLink(l1, 0, 1);
        int num2 = getNumByLink(l2, 0, 1);


        return getlinkByNum(num1 + num2);


    }

    /**
     * 递归解析链表
     *
     * @param listNode
     * @param num
     * @param index
     * @return
     */
    private static int getNumByLink(ListNode listNode, int num, int index) {
        if (listNode != null) {
            return getNumByLink(listNode.next, num + listNode.val * (int) Math.pow(10, index), index + 1);
        }
        return num;
    }

    /**
     * 递归生成链表
     *
     * @param num
     * @return
     */
    private static ListNode getlinkByNum(int num) {

        ListNode listNode = new ListNode(num % 10);

        if (num / 10 != 0) {
            listNode.next = getlinkByNum(num / 10);
        }
        return listNode;

    }

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();


        //答案方法
        int n = s.length(), ans = 0;
        // current index of character
        Map<Character, Integer> map = new HashMap<>();
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }


        //我的方法
        int num = 0;

        String string = null;
        for (int i = 0, len = chars.length; i < len; i++) {
            string = new String();
            string += chars[i];

            for (int j = i + 1; j < len; j++) {
                if (string.indexOf(chars[j]) == -1) {
                    string += chars[j];
                } else {
                    break;
                }
            }

            num = num > string.length() ? num : string.length();

        }

        return num;
    }


    /**
     * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
     * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len = nums1.length + nums2.length;

        int remainder = len % 2;

        int[] allNums = new int[len];

        int index = 0, position = len / 2 + 1, i = 0, j = 0;

        double out = 0.0;


        while (index <= position) {

            int num=0,num1=0,num2=0;
            if (i < nums1.length) {
                num1 = nums1[i];
            }
            if (j < nums2.length) {
                num2 = nums2[j];
            }
            if(i<=j){
                allNums[index] = num1;
                i++;
            }else{
                allNums[index] = num2;
                j++;
            }
            index++;
        }

        if(remainder==1){
            out = allNums[position]*1.0;
        }else{
            out = (allNums[position-1]+allNums[position])/2.0;
        }

        return out;
    }

    /**
     *
     * @param rental
     */
    public static void cpmplex(double rental){

        for (int i = 1; i < 31; i++) {
            double singleYear = (rental+3*i)/i;

            double allNum = 0.0;
            for (int j = 0; j < i; j++) {
                allNum+=singleYear/Math.pow(0.98,j);
            }

            System.out.println("对应数据=="+"年份："+i+"总额度："+singleYear*i+"累计贬值额度："+allNum);

        }

    }

    public static void main(String[] args) {

        cpmplex(100);

    }


}
